What's an algorithm?

	set of instructions the computer will follow to solve a problem


Suppose you need an algorithm to solve a particular problem.
If there are several competing algorithms, each of which of which
solves the problem correctly, how do you go about choosing the
particular algorithm you will use in your program?

	it depends on what you are trying to optimize
	1. running time
	2. memory or disk space
	3. programmer time

	memory and disk space are cheap

	you should use the simplest algorithm that meets your requirements

	often there is tension between simplicity and efficiency

	start simple, only add complexity when needed


How do you measure the running time of an algorithm?

	implement all of the candidate algorithms
	run each on all possible inputs
	pick a representative set of inputs (benchmark)
	run each algorithm on the benchmark

	mathematically analyze each algorithm on paper
	predict performance on expected inputs


How does input size affect running time?

	sorting 10000 items should take longer than sorting 10 items


What's T(N)?

	the number of time units an algorithm uses given an input of size N.


What's T(N) for the following method?
(Assume each statement uses one time unit.)

	double mean (double[] a, int n) {
	    double sum = 0;
	    for (int i = 0; i < n; i++)
	        sum += a[i];
	    double mean = sum / count;
	    return mean;
	}

	T(N) = 1 + 1 + (n+1) + n + n + 1 + 1 = 3n + 5



Big Oh


Suppose you have T(N) = N^2 + 2N + 4
Does it make sense to define T(N) this precisely?

	NO
	1. when N is large, the high-order term dominates
		N^2 + 2N + 4 = 1002004 when N is 1000
	2. when N is small, time is not an issue
	3. constant factors depend on machine and compiler


How do you capture the dominant term of T(N)?

	use Big Oh notation
	abstraction of time formula
	keep the dominant term
	drop low-order terms
	drop constants


Common BigOh Functions

	O(1)		constant
	O(log N)	logrithmic
	O(N)		linear
	O(NlogN)	NlogN
	O(N^2)		quadratic
	O(N^3)		cubic
	O(2^N)		exponential